/**
 * 
 */
package BNS.coloring;

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;
import java.util.Vector;

import BNS.graphs.MatrixGraph;

/**
 * @author iggardne
 *
 */
public class Simulation {
	private final int NUM_STEPS;
	public static final boolean DEBUG = false;
	private final SimuGraph gr;
	private final int numNodes;
	private int chroma;
	private int steps;
	private int solutions;
	private final Vector<SimuNode> nodes;
	private final Vector<Vector<SimuNode>> neighbors;
	private final Vector<SimuEdge> edges;
	//private Vector<Integer> colors;
	
	/**
	 * This sets up the graph and the data structures (neighbors vector)
	 * that are used for the chromatic number and simulation algorithms.
	 * 
	 * @param file - contains a graph in adjacency matrix form.
	 * @param chroma - the chromatic number of the graph (if known)
	 * @param s - the number of steps to run a simulation
	 */
	public Simulation(File file,int chroma,int s) {
		gr=new SimuGraph(MatrixGraph.create(file));
		nodes=gr.nodes;
		edges=gr.edges;
		numNodes=nodes.size();
		this.chroma=chroma;
		NUM_STEPS=s;
		
		//create the vectors that will hold the neighbors of each node
		neighbors=new Vector<Vector<SimuNode>>();
		for(int i=0;i<nodes.size();i++)
			neighbors.add(new Vector<SimuNode>());
		
		//add node to to node from's neighbor vector
		//add node from to node to's neighbor vector
		for(SimuEdge e:edges) {
			neighbors.get(e.from.index).add(e.to);
			neighbors.get(e.to.index).add(e.from);
		}
		
		
		/*for(Node n:nodes) {
			System.err.print(n.getIndex()+": neighbors are:");
			for(Node ne:neighbors.get(n.getIndex()))
				System.err.print(" "+ne.getIndex());
			System.err.println();
		}*/
	}
	
	/**
	 * check if node has any neighbors that are color. If yes return false,
	 * if no return true;
	 * 
	 * @param node - the node to check the neighbors of
	 * @param color - the color to check the neighbors against
	 * @return
	 */
	public boolean available(int node,int color) {
		for(SimuNode curr:neighbors.get(node))
			if(curr.color==color) return false;
		return true;
	}
	
	/**
	 * This method finds the chromatic number of a graph.
	 * It starts at chroma and then recursively calls itself, with chroma
	 * plus one until it finds the chromatic number.
	 * 
	 * @param chroma - the first chromatic number to check
	 * @return the chromatic number of the current graph
	 */
	public int chromaticNumber(int chroma) {
		if(chroma==nodes.size()) return nodes.size();
		
		this.chroma=chroma;
		
		//Node node=nodes.get(0);node.
		System.out.println("Colors:"+chroma);
		
		if(chromaColorable(0)) return chroma;
		
		return chromaticNumber(chroma+1);
	}
	
	/**
	 * Recursive function to find if a graph can be colored with chroma
	 * colors. It is a brute force algorithm that only checks possible
	 * combinations.
	 * 
	 * @param node - the next node to check
	 * @return - true if the graph is colorable false otherwise
	 */
	public boolean chromaColorable(int node) {
		if(node==nodes.size()) return true;
		
		for(int i=1;i<=chroma;i++) {
			if(available(node,i)) {
				//System.err.println(node+":"+i);
				nodes.get(node).color=i;
				if(chromaColorable(node+1)) return true;
			}
		}
		//if(node<=2) System.out.println(chroma+": Exiting: "+node);

		nodes.get(node).color=0;
		return false;
	}
	
	public void solutions(int node) {
		//System.err.println("entering "+node);
		
		if(node==nodes.size()) {
			//if(gr.colored(true)) {
			solutions++;
			//for(Node n:nodes)
			//	System.err.print(n.getIndex()+1+":"+n.color+" ");
			//System.err.println();
			//}
			return;
		}
		else { 
		for(int i=1;i<=chroma;i++) {
			if(available(node,i)) {
				//System.err.println(node+":"+i);
				nodes.get(node).color=i;
				solutions(node+1);
			}
		}
		}
		nodes.get(node).color=0;
		//System.err.println("leaving "+node);
	}
	/*
	public void testColorability() {
		setColor(0);
	}
	
	public void setColor(int node) {
		//System.err.println("entering "+node);
		if(node==nodes.size()) {
			if(gr.colored(true)) {
				for(Node n:nodes)
					System.err.print(n.getIndex()+":"+n.color+" ");
				System.err.println();
			}
		}
		else for(int i=1;i<=chroma;i++) {
			nodes.get(node).color=i;
			setColor(node+1);
		}
		//System.err.println("leaving "+node);

	}
	
	/**
	 * Runs a simulation at the current existing state.
	 * 
	 * @return
	 */
	public boolean runSimulation() {

		Random rand=new Random();
		int next, minColorNum, colorChoice;
		SimuNode n;
		int neighborColors[];
		Vector<Integer> minColors;
		
		
		if(DEBUG)System.err.println("Start Simulation ----------------------");
		
		for(steps=0;steps<NUM_STEPS;steps++) {
			
			/**
			 * random number [0 - numNodes) numNodes is usually 16
			 */
			next=rand.nextInt(numNodes);
			
			n=nodes.get(next);
			//color=n.color;
			neighborColors=new int[chroma+1];
			
			//set the amount of neighbors set at each color
			for(SimuNode ne:neighbors.get(next))
				neighborColors[ne.color]++;
			
			//find the color with the least neighbors set at
			minColorNum=numNodes;
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]<minColorNum) minColorNum=neighborColors[j];
			
			//put all the colors with equally small amounts in vector
			minColors=new Vector<Integer>();
			for(int j=1;j<=chroma;j++)
				if(neighborColors[j]==minColorNum) minColors.add(j);
			
			//find out the random number choice
			/**
			 * random number [0 - minColors.size()) always small 2 or 3 usually
			 */
			colorChoice=minColors.size()>1 ? rand.nextInt(minColors.size()) : 0;
			
			//change to the chosen color
			n.color=minColors.get(colorChoice);
			
			
			if(DEBUG) {
			System.err.print("Step - "+steps+". Node - "+n+":"+next+" - ");
			for(int x:neighborColors) {
				System.err.print(x+" ");
			}
			
			
			System.err.println();
			for(SimuNode n2:nodes)
				System.err.print(n2+":"+n2.color+", ");
			System.err.println();
			}
			

			if(gr.wellColored()) {
				for(SimuNode currentNode:nodes) {
					System.out.print(currentNode+":"+currentNode.color+" "+
							(currentNode.index<10?" ":"")+
							(currentNode.color<10?" ":""));
					if(currentNode.index%10==0) System.out.println();
				}
				System.out.println();
				return true;
			}
			
			//System.exit(0);
		}
		
		return false;
		/*
		if(gr.colored(true)) System.err.println("Graph solved in steps: "+(++i));
		else System.err.println("Graph NOT solved in steps: "+i+" : "+NUM_STEPS);
		
		return i;
		*/
	}
	
	
	/**
	 * Sets the initial condition of the graph so that another simulation can be
	 * run without needing to recreate all the data structures.
	 */
	public void init() {
		
		gr.init();
		
		if(DEBUG) for(SimuNode n:nodes) {
			System.err.print(n+": neighbors are:");
			for(SimuNode ne:neighbors.get(n.index))
				System.err.print(" "+ne);
			System.err.println();
		}
	}
	
	/**
	 * Runs multiple simulations.
	 * 
	 * @param number - the number of simulations to run.
	 */
	public void runSimulations(int number) {
		int totalSteps=0,totalSuccesses=0;
				
		for(int i=0;i<number;i++) {
			init();
			
			if(runSimulation()) {
				if(DEBUG)System.err.println(steps);
				totalSteps+=steps;
				totalSuccesses++;
			}
		}

		System.err.printf("Running %d simulations at %d steps./n",number,NUM_STEPS);
		System.err.printf("Average Success Rate: %f. Averages Steps per Success %f\n",totalSuccesses/(double)number,totalSteps/(double)totalSuccesses);	
	}

	/**
	 * Creates a random graph for testing purposes.
	 * 
	 * @param size - the size of the graph
	 * @param fileName - the file to write the adjacency matrix to.
	 */
	public void writeTest(int size, String fileName) {
	    BufferedWriter file;
	    Random rand=new Random();
	    try {
			file = new BufferedWriter(new FileWriter(new File("matrix/"+fileName+".matrix")));
			for(int i=0;i<size;i++) {
				for(int j=0;j<size;j++)
					file.write(i!=j && rand.nextBoolean()?"1 ":"0 ");
				file.newLine();
			}
				
			file.close();	
				
			} catch(IOException e) {
				System.err.println("Error while opening file.");
				e.printStackTrace();
			}
	}

	/** The main driver; invoke this from the command line to start the process. 
	Supply it with 2 arguments: the name of the matrix file and the number of
	colors to simulate a test with.
	 * @throws IOException 
	*/
	public static void main(String[] args) throws IOException { 
		if (args.length==0) {
			System.err.println("argument must be the name of a .matrix file");
			System.exit(01);
			}
		String fname= args[0];
		File f= new File(fname);
		if (!f.exists()) {
			System.err.println("the matrix file did not exist");
			System.exit(02);
			}
		
		if (args.length<2) {
			System.err.println("must supply the number of colors");
			System.exit(01);
			}
		//set the default flags
		int color = Integer.parseInt(args[1]);
		

		Simulation s=new Simulation(f,color,100000);
		
		SimuGraph gr=new SimuGraph(new MatrixGraph(f));
		
		gr.findClique();

		/*File folder=new File("matrix");
		
		for(File file:folder.listFiles()){
			if(file.isHidden()) continue;
			Simulation s1=new Simulation(file,color,100000);
			System.out.println(file.getName()+":"+s1.chromaticNumber(0));
		}
		*/		
	}
	
	/**
	 * chrmatic number checking code
	 */
	/*
	Simulation s = new Simulation(f,color,1000);
	//for(int x=0;x<6;x++)
	//s.runSimulations(1000);
	
	//File folder = new File("matrix");

	ThreadMXBean bean = ManagementFactory.getThreadMXBean( );
	        
	double totalTime;
	long time=0;
	long start=bean.getCurrentThreadCpuTime();
	int chrNum;
	int totalChroma;
	
	int ITERS=100;
	
	BufferedWriter out=new BufferedWriter(new FileWriter(new File("info")));
	
	//for(File file:folder.listFiles()) if(!file.isHidden()){
	
	for(int i=44;i<=100;i++) {
		totalTime=0;
		totalChroma=0;
		for(int j=0;j<ITERS;j++) {
			s.writeTest(i,"test");
			f=new File("matrix/test.matrix");
			s=new Simulation(f,color,10);	
		
			start=bean.getCurrentThreadCpuTime();
			chrNum=s.chromaticNumber(1);
			time=bean.getCurrentThreadCpuTime()-start;
			totalTime+=time/(float)1000000000;
			totalChroma+=chrNum;
			
			out.write("NumNodes: "+s.numNodes+" ChrNum:"+chrNum+" @ "+time/(float)1000000000+"\n");
			out.flush();
		}
		
		System.out.println("NumNodes: "+i+" AverageChr: "+totalChroma/(float)ITERS+" AverageTime: "+totalTime/(float)ITERS);
		

	}
	out.close();
	*/
	/*File folder=new File("matrix");
	
	for(File file:folder.listFiles()){
		if(file.isHidden()) continue;
		Simulation s=new Simulation(file,color,100000);
		System.out.println(file.getName()+":"+s.chromaticNumber(0));
	}
	*/
	
	
}
